{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #文件组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #two-pointers #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #双指针 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fileCombination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #文件组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 <strong>正整数</strong>（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 <code>target</code> 的所有文件。请返回所有符合该要求的文件传输组合列表。</p>\n",
    "\n",
    "<p><strong>注意</strong>，返回时需遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每种组合按照文件编号 <strong>升序</strong> 排列；</li>\n",
    "\t<li>不同组合按照第一个文件编号 <strong>升序</strong> 排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 12\n",
    "<strong>输出：</strong>[[3, 4, 5]]\n",
    "<strong>解释：</strong>在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 18\n",
    "<strong>输出：</strong>[[3,4,5,6],[5,6,7]]\n",
    "<strong>解释：</strong>在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 10^5</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof](https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof](https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12', '18']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "\n",
    "        # 滑动窗口\n",
    "        i, j, s, res = 1, 2, 3, []\n",
    "        while i < j:\n",
    "            if s == target:\n",
    "                res.append(list(range(i, j + 1)))\n",
    "            if s >= target:\n",
    "                s -= i\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i, j, s, res = 1, 2, 3, []\n",
    "        while i < j:\n",
    "            if s == target:\n",
    "                res.append(list(range(i, j+1)))\n",
    "            if s > target:\n",
    "                s -= i\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int):\n",
    "        i, j, res = 1, 2, []\n",
    "        while i < j:\n",
    "            j = (-1 + (1 + 4 * (2 * target + i * i - i)) ** 0.5) / 2\n",
    "            if i < j and j == int(j):\n",
    "                res.append(list(range(i, int(j) + 1)))\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i, j, s, res = 1,2,3,[]\n",
    "\n",
    "        while i < j:\n",
    "            if s == target:\n",
    "                res.append(list(range(i, j+1)))\n",
    "\n",
    "            if s > target:\n",
    "                s -= i\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                s += j\n",
    "                \n",
    "                \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i,j,res=1,2,[]\n",
    "        while i<j:\n",
    "            j=(-1+(1+4*(2*target+i*i-i))**0.5)/2\n",
    "            if i<j and j== int(j):\n",
    "                res.append(list(range(i,int(j)+1)))\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        left,right=1,2\n",
    "        count=3\n",
    "        res=[]\n",
    "        while left < right:\n",
    "            if count == target:\n",
    "                res.append(list(range(left,right+1)))\n",
    "          \n",
    "            if count >= target: \n",
    "                count-=left\n",
    "                left+=1\n",
    "            else:\n",
    "                right+=1\n",
    "                count+=right  \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i = 1\n",
    "        j = 2\n",
    "        s = 3\n",
    "        res = []\n",
    "        while ((2*j)-1) <= target:\n",
    "            if s < target:\n",
    "                j += 1\n",
    "                s += j\n",
    "            elif s > target:\n",
    "                i += 1\n",
    "                s -= i - 1\n",
    "            else:\n",
    "                res.append(list(range(i, j+1)))\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i, j, s, res = 1, 2, 3, []\n",
    "        while i < j:\n",
    "            if s == target:\n",
    "                res.append(list(range(i, j + 1)))\n",
    "            if s >= target:\n",
    "                s -= i\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        # 滑动窗口法\n",
    "        i, j, s, res = 1, 2, 3, []\n",
    "        while i < j:\n",
    "            if s == target:\n",
    "                res.append(list(range(i, j + 1)))\n",
    "            if s >= target:\n",
    "                s -= i\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        left, right = 1, 1\n",
    "        window_sum = 1\n",
    "        while right < target // 2 + 2 and left <= right:\n",
    "            if window_sum == target:\n",
    "                if right - left >= 1:\n",
    "                    ans.append([i for i in range(left, right + 1)])\n",
    "                right += 1\n",
    "                window_sum += right\n",
    "            elif window_sum > target:\n",
    "                window_sum -= left\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "                window_sum += right\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        # 整数拆分\n",
    "        # 思路一：暴力法\n",
    "        temp = []\n",
    "        for i in range(1,target):\n",
    "            for k in range(target):\n",
    "                if (k+1)*i + k*(k+1)/2 == target:\n",
    "                    temp.append([i,k])\n",
    "                elif (k+1)*i + k*(k+1)/2 > target:\n",
    "                    break\n",
    "        return [list(range(a[0],a[0]+a[1]+1)) for a in temp]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        # 整数拆分\n",
    "        # 思路一：暴力法\n",
    "        # temp = []\n",
    "        # for i in range(1,target):\n",
    "        #     for k in range(target):\n",
    "        #         if (k+1)*i + k*(k+1)/2 == target:\n",
    "        #             temp.append([i,k])\n",
    "        #         elif (k+1)*i + k*(k+1)/2 > target:\n",
    "        #             break\n",
    "        # return [list(range(a[0],a[0]+a[1]+1)) for a in temp]\n",
    "        # 思路二：公式法-增加约束条件\n",
    "        temp = []\n",
    "        for i in range(1,target):\n",
    "            k = 0\n",
    "            while k <= 2*target//(k+1)-2*i:\n",
    "                if (i+k/2)*(k+1) == target:\n",
    "                    temp.append([i,k])\n",
    "                elif (i+k/2)*(k+1) > target:\n",
    "                    break\n",
    "                k+=1\n",
    "        return [list(range(a[0],a[0]+a[1]+1)) for a in temp]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        left = 1 \n",
    "        right = 2\n",
    "        s = 3\n",
    "        while left < right  :\n",
    "            if s  == target :\n",
    "                result.append(list(range(left, right +1)))\n",
    "            if s >= target:\n",
    "                s -= left\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "                s += right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(1,target//2+1):\n",
    "            n = i \n",
    "            for j in range(i+1,target):\n",
    "                if n > target:\n",
    "                    break\n",
    "                elif n == target:\n",
    "                    ans.append([x for x in range(i,j)])\n",
    "                n += j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        if target == 1:\n",
    "            return []\n",
    "        l, r = 1, 2\n",
    "        now = 3\n",
    "        ans = []\n",
    "        while l < r :\n",
    "            if now > target:\n",
    "                now -= l\n",
    "                l += 1\n",
    "            elif now == target:\n",
    "                # print(l, r+1)\n",
    "                ans.append(list(range(l, r+1)))\n",
    "                now -= l\n",
    "                l += 1\n",
    "            else :\n",
    "                r += 1\n",
    "                now += r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i = 1\n",
    "        j = 2\n",
    "        s = 3\n",
    "        res = []\n",
    "        while i < j:\n",
    "            if s < target:\n",
    "                j += 1\n",
    "                s += j\n",
    "            elif s > target:\n",
    "                i += 1\n",
    "                s -= i - 1\n",
    "            else:\n",
    "                res.append(list(range(i, j+1)))\n",
    "                j += 1\n",
    "                s += j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int):\n",
    "        i, j, res = 1, 2, []\n",
    "        while i < j:\n",
    "            j = (-1 + (1 + 4 * (2 * target + i * i - i)) ** 0.5) / 2\n",
    "            if i < j and j == int(j):\n",
    "                res.append(list(range(i, int(j) + 1)))\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        sum, j = 0, 1\n",
    "        result = []\n",
    "        for i in range(1, target//2 + 2):\n",
    "            sum += i\n",
    "            if sum == target:\n",
    "                result.append(list(range(j, i + 1)))\n",
    "            elif sum > target:\n",
    "                while sum > target:\n",
    "                    sum -= j\n",
    "                    j += 1\n",
    "                    print(j,i,sum)\n",
    "                if sum == target:\n",
    "                    result.append(list(range(j, i + 1)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        # from 1 to start, end with target\n",
    "        for _ in range(target):\n",
    "            if (_ == 0):\n",
    "                continue\n",
    "            arr = Solution.searchValues(self, _, target, [])\n",
    "            if (arr):\n",
    "                res.append(arr)\n",
    "        return res\n",
    "\n",
    "    def searchValues(self, val: int, target: int, arr: List[int]) -> List[int]:\n",
    "        if (sum(arr)+val > target):\n",
    "            return\n",
    "        if (sum(arr) > target):\n",
    "            return None\n",
    "        if (val > target):\n",
    "            return None\n",
    "        arr.append(val)\n",
    "        if (val < target and sum(arr) < target):\n",
    "            return Solution.searchValues(self, val+1, target, arr)\n",
    "        if (val < target and sum(arr) == target):\n",
    "            return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in range(1,target//2+1):\n",
    "            self.backtracking(i,i,[i],target,res)\n",
    "        return res\n",
    "    def backtracking(self,l, temp, Lis,target,res):\n",
    "        if temp > target:\n",
    "            return\n",
    "        if temp == target and len(Lis) >= 2:\n",
    "            res.append(Lis)\n",
    "            return\n",
    "        else:\n",
    "            self.backtracking(l+1, temp+l+1, Lis+[l+1],target,res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        j = 0\n",
    "        sub_sum = 0\n",
    "        res = []\n",
    "        nums = [k for k in range(1, int(target / 2) + 2)]\n",
    "        for i in nums:\n",
    "            sub_sum += i\n",
    "            while j < i and sub_sum > target:\n",
    "                sub_sum -= nums[j]\n",
    "                j += 1\n",
    "            if sub_sum == target and i - j > 0:\n",
    "                res.append(nums[j:i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        双指针划一下就好\n",
    "        \"\"\"\n",
    "        nums = list(range(1, (target+1)//2+1))\n",
    "        l = 0\n",
    "        s = 0\n",
    "        R = []\n",
    "        # [l, r]区间的值小于等于target\n",
    "        for r in range(0, len(nums)):\n",
    "            s += nums[r]\n",
    "            while s > target:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            if s == target and r > l:\n",
    "                R.append(nums[l:r+1])\n",
    "        return R   \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        lis = []\n",
    "        res = []\n",
    "        for i in range(1,math.ceil(target//2)+2):\n",
    "            lis.append(i)\n",
    "        for i in range(1,len(lis)):\n",
    "            n = i\n",
    "            tot = 0\n",
    "            while tot < target:\n",
    "                tot += n\n",
    "                n += 1\n",
    "            if tot == target:\n",
    "                res.append(lis[i-1:n-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        lis = []\n",
    "        res = []\n",
    "        for i in range(1,math.ceil(target/2)+2):\n",
    "            lis.append(i)\n",
    "        for i in range(1,len(lis)):\n",
    "            n = i\n",
    "            tot = 0\n",
    "            while tot < target:\n",
    "                tot += n\n",
    "                n += 1\n",
    "            if tot == target:\n",
    "                res.append(lis[i-1:n-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        n = [i for i in range(1,target//2+2)]\n",
    "        i = 0\n",
    "        a = []\n",
    "        while i<len(n):\n",
    "            j = i+1\n",
    "            tmp = n[i]\n",
    "            while tmp <target and j<len(n):\n",
    "                tmp += n[j]\n",
    "                j += 1\n",
    "                if tmp > target:\n",
    "                    break\n",
    "            if tmp == target:\n",
    "                n1 = [k for k in range(i+1,j+1)]\n",
    "                a.append(n1)\n",
    "            i += 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fileCombination(self, target: int) -> List[List[int]]:\n",
    "        i, j = 0, 1\n",
    "        ret = []\n",
    "        mid = target // 2 + 2\n",
    "        nums = list(range(1, mid))\n",
    "        print(nums)\n",
    "        while i <= mid - 1 and j <= mid:\n",
    "            total = sum(nums[i:j])\n",
    "            print(total)\n",
    "            if total > target:\n",
    "                i+=1\n",
    "            elif total < target:\n",
    "                j+=1\n",
    "            else:\n",
    "                ret.append(nums[i:j])\n",
    "                i+=1\n",
    "                j+=1\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
